//***********************************************************
//*
//* File:           DumbPlayer.java
//* Author:         Abhinav Kamra
//* Contact:        kamra@cs.columbia.edu
//* Update:         10/03/2004
//*
//* Description:    Dump player for Project 2.  Purely for
//*                 didactic purposes.
//*
//***********************************************************

package paths.g4;

import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.image.*;

import javax.imageio.*;

import paths.*;

public final class P2 implements IFCPlayer {

  static Random _random;
  static final String _CNAME = "G4 Player2";
  static final Color  _CCOLOR = new Color(0.8f, 0.2f, 0.4f);

  Maps _maps;
  ArrayList<City> cities;
  ArrayList<Link> links;
  boolean[][] reachable_links;
  boolean[][] city_connected;
  boolean[][] dominant_links;
  boolean[][] example_links;
  String start_city_name;
  int start_city_idx;
  City start_city;
  int in_degree[];
  int out_degree[];
  int num_city;
  int sizee;
  String cityReachable[];
  String cityPrintedout[];
  String description[]=new String[5];
  boolean cityReach[];
  ArrayList<Integer> route1;
  ArrayList<Integer> route2;
  boolean finalcity[];
  enum GRAPH_TYPE{WHOLE_MAP, DETAILED_MAP};

  String zoominDescrip = new String();

  public void register(Maps __maps) throws Exception {
    _maps = __maps;
    cities = _maps.getCities();
    links = _maps.getLinks();
    num_city = cities.size();
 sizee=0;
    cityReachable=new String[num_city];
    cityPrintedout=new String[num_city];
    cityReach=new boolean[num_city];
    finalcity=new boolean[num_city];
    example_links = new boolean[num_city][num_city];
  }

  public Move move() throws Exception {
    BufferedImage image;

    //File file = _maps.getBackgroundImage();
    File file = new File("GameFiles/G4-background.png");

    //to get the background image, do this
    image = ImageIO.read(file);

    //get graphics to draw on the image.
    Graphics2D g = image.createGraphics();
    g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                       RenderingHints.VALUE_ANTIALIAS_ON);

    // Search the graph
    start_city_name = _maps.getStart().name;
    start_city_idx = Util.getCityIdxByName(start_city_name, cities);
    start_city = cities.get(start_city_idx);
    reachable_links =
        Util.FindAllPossibleRoutes(cities, links, start_city_name);
    Util.removeShortRoutes(reachable_links, start_city_idx);
    in_degree = Util.getInDegree(reachable_links);
    out_degree = Util.getOutDegree(reachable_links);
    city_connected = Util.runWarshall(reachable_links, start_city_idx);
    dominant_links = Util.getDominantLinks(city_connected, start_city_idx);

    int pp=0,jj=0;
    for(jj=0;jj< num_city;jj++)
    {
    	cityReach[jj]=false;
    }
    for(jj=0;jj< num_city;jj++)
    {
    	finalcity[jj]=false;
    }
    
    for(int cc=0;cc<num_city;cc++)
    {
    	if(in_degree[cc]>0)
    	{
    		cityReach[cc]=true;
    		City d=cities.get(cc);
    		cityReachable[cc]=d.name;
    		//pp++;
    	}
    }
   
    g.setColor(Color.BLACK);
    g.fillRect(0, 0, page_width, example_route_height + 10 + 50);
    drawAroundTheWorldText(
        (Graphics2D) g.create(0, example_route_height + 10, page_width, 50));

    drawExampleRoutes(
        (Graphics2D) g.create(18, 10, page_width, example_route_height));

    drawGraph((Graphics2D) g.create(5, 246, graph_width + 30, graph_height),
              GRAPH_TYPE.WHOLE_MAP, graph_width, graph_height);

    g.setColor(Color.BLACK);
    g.drawLine(20, 587, 55, 587);
    g.drawString("Longest Route", 60, 593);

    g.setColor(Color.WHITE);
    g.drawLine(170, 587, 205, 587);
    g.setColor(Color.BLACK);
    g.drawString("Other Possible Routes", 210, 593);

    g.setColor(Color.BLACK);
    g.fillOval(360, 587, 4, 4);
    g.drawString("Possibly Reachable Cities", 370, 593);

    g.setFont(new Font("SansSerif", Font.BOLD, 20));
    g.setColor(Color.red);
    g.drawString("One Ticket, One Price.", 20, 850);
    g.setFont(new Font("SansSerif", Font.BOLD, 16));
    g.setColor(Color.BLACK);
    g.drawString("For more information, visit our website http://yal.com/", 20, 875);
    g.setColor(Color.RED);
    g.drawString("Possibilities Unlimited!!!!", 20, 897);

    Graphics2D zoom_graphics =
        (Graphics2D) g.create(10, 600, zoom_graph_width, zoom_graph_height);
    drawZoomInMap(zoom_graphics, zoom_graph_width, zoom_graph_height);

    g.setFont(new Font("SansSerif", Font.PLAIN, 12));
    g.setColor(Color.BLACK);
    if (!zoominDescrip.equals("")){
      zoominDescrip += " Region";
      g.drawString(zoominDescrip, 20, 810);
    }   

    drawOtherCities((Graphics2D) g.create(zoom_graph_width + 10, 600, page_width - zoom_graph_width - 20, 200));
    
    g.setColor(Color.BLACK);
    g.setFont(new Font("SansSerif", Font.BOLD, 16));
    g.drawString("Or Customize Your Dream Route!", 13, 260);


    Move RET = new Move(image, "G4Result");
    return RET;
  }

  void addToExampleLinks(ArrayList<Integer> route) {
    for (int i = 0; i < route.size(); i++) {
      System.out.println("add example links " + route.get(i) + " " + route.get((i + 1) % route.size()));
      example_links[route.get(i)][route.get((i + 1) % route.size())] = true;
    }
  }

  private void drawZoomInMap(Graphics2D g, int window_width, int window_height) {
    boolean city_reachable[] = new boolean[num_city];
    for (int i = 0; i < num_city; i++)
      city_reachable[i] = in_degree[i] > 0;
    ZoomIn zoom_in = new ZoomIn();
//    ZoomIn.Area area = zoom_in.findCrowdArea(cities, city_reachable);
    ZoomIn.Area area = zoom_in.findCrowdArea(cities, city_reachable, in_degree);

    //no area needed to zoom in
    if(area == null)
    	return;

    zoominDescrip += area.name;

    float left = mapX(area.x, 1);
    float right = mapX(area.x + area.width, 1);
    float top = mapY(area.y, 1);
    float bottom = mapY(area.y - area.height, 1);
    float entire_map_width = window_width / (right - left);
    float entire_map_height = window_height / (bottom - top);
    g.setClip(2, 2, window_width - 4, window_height - 4);
    g.translate(-left * window_width / (right - left),
                -top * window_height / (bottom - top));

    drawGraph(g, GRAPH_TYPE.DETAILED_MAP, entire_map_width, entire_map_height);
    g.translate(left * window_width / (right - left),
                top * window_height / (bottom - top));
    g.setClip(0, 0, window_width, window_height);
    g.setColor(new Color(20, 20, 120));
    g.drawRoundRect(2, 2, window_width - 4, window_height - 4, 6, 6);
  }

  private void drawAroundTheWorldText(Graphics2D g) throws IOException {
	    File file = new File("GameFiles/G4-around-the-world.png");
	    BufferedImage image = ImageIO.read(file);
	    g.drawImage(image, 200, 0, null, null);
	  }
  private String routeToString(ArrayList<Integer> route)  {
	  try{
	     String route_str = "";
	     String route_str2 = "";
//    final int OMIT_THRESHOLD = 15;
    final int OMIT_THRESHOLD = 13;
    int k=0;
    
    
    if (route.size() <= OMIT_THRESHOLD) {
      for (Integer i : route) {
        route_str += cities.get(i).name + " -> ";
    k=Util.getCityIdxByName(cities.get(i).name, cities);
       // cityPrintedout[k]=cities.get(i).name;
    //k++;
      }
      sizee=k;

      route_str += start_city_name;

      if(route_str.length() < 2*95)
    	  return route_str;
      else
    	  route_str = "";
    }
    
//    else
//    {
    	int cityNum = 0;
    	//up to 7 cities
        for (int i = 0; i < 7; i++)
//      for (int i = 0; i < 7; i++)
      {
        route_str += cities.get(route.get(i)).name + " -> ";
        k=Util.getCityIdxByName(cities.get(route.get(i)).name, cities);
        // cityPrintedout[k]=cities.get(i).name;
         cityNum ++;
         //if the length is too large, cut the number
         if(route_str.length() >= 98){
        	 break;
         }
      }
        //make it long first
        int num = 8;
        route_str2 = "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    while(route_str2.length() >= 98){
    	route_str2 = "";
        route_str2 += " (" + (route.size() - OMIT_THRESHOLD + num - cityNum ) + " More Cities) -> ";
        
        //(n omitted) + up to 5 cities + end city (up to 7)
        for (int i = route.size() - OMIT_THRESHOLD + num; i < route.size(); i++)
//        for (int i = route.size() - OMIT_THRESHOLD + 3 + 7; i < route.size(); i++)
        {
      	  route_str2 += cities.get(route.get(i)).name + " -> ";
      	  k=Util.getCityIdxByName(cities.get(route.get(i)).name, cities);
            // cityPrintedout[k]=cities.get(i).name;
        }
        sizee=k;
        route_str2 += start_city_name;

        if(route_str2.length() >= 98)
        	num ++;
        if (route.size() - OMIT_THRESHOLD + num == route.size()-1)
            break;
    }
//    } //end of else

    route_str += route_str2;

    return route_str;
    
	  }
	  catch(Exception e)
	  {
		  return null; 
	  }
	  }

  private int drawMultilineExampleRoute(String str, Graphics2D g, int x, int y) {
    String[] stops = str.split(" -> ");
    String output = "";
    String newOutput = "";
    int current_line_width = 0;
    for (int i = 0; i < stops.length; i++) {
      if (i != stops.length - 1)
        output += stops[i] + " -> ";
      else
        output += stops[i];
      
      if (i == stops.length - 1) ;
      else if (i+1 != stops.length - 1)
    	  newOutput = stops[i+1] + " -> ";
      else
    	  newOutput = stops[i+1];
      if (output.length() > 85 || i == stops.length - 1
    		  || output.length() + newOutput.length() > 98) {
//      if (output.length() > 70 || i == stops.length - 1) {
        g.drawString(output, x, y);
        y += 15;
        output = "";
      }
    }
    return y;
  }

  private void drawExampleRoutes(Graphics2D g) {
    int ll=0;
    
	  ArrayList<Integer> longest_route =
        Util.findLongestRoute(cities, reachable_links, start_city_idx);
    String longest_route_str = routeToString(longest_route);
while(longest_route_str==null)
{
	longest_route =
        Util.findLongestRoute(cities, reachable_links, start_city_idx);
     longest_route_str = routeToString(longest_route);
	
}
    ArrayList<City> routee=new ArrayList<City>();
    addToExampleLinks(longest_route);
    for (int i = 0; i < longest_route.size() ; i++) {
      routee.add(cities.get(longest_route.get(i)));
      if (longest_route_str.indexOf(cities.get(longest_route.get(i)).name) != -1)
        finalcity[longest_route.get(i)] = true;
    }
    String long_route_descript=CityMetadata.getMetaResult(routee);
    
    g.setColor(Color.red);
    g.setFont(new Font("SansSerif", Font.BOLD, 18));
    g.drawString("It's Time for The Most Refereshing Tour of Your Life !!!", 10, 15);
    
    long_route_descript+="-- Covering Upto ";
    long_route_descript+=routee.size();
    long_route_descript+=" Cities";
    g.setColor(Color.WHITE);
    g.setFont(new Font("SansSerif", Font.BOLD, 12));
    g.drawString("Longest Route and "+long_route_descript, 5, 35);
    g.setFont(new Font("SansSerif", Font.PLAIN, 12));
    int y = 55;
    y = drawMultilineExampleRoute(longest_route_str, g, 5, y);
    ArrayList<String> drawn_routes = new ArrayList<String>();
    drawn_routes.add(longest_route_str);
    ArrayList<String> existing_route_description = new ArrayList<String>();
    
    for (int n = 0; n < 2; n++) {
    	ArrayList<Integer> route = null;
      String route_str = null;
      String descript = null;
      int min_route_length = Math.min(6, longest_route.size());
      boolean can_find_a_route = true;
      int num_trail = 0;
      do {
        route = Util.FindRandomRoute(reachable_links, start_city_idx);
        if (route != null) {
      	  route_str = routeToString(route);
          ArrayList<City> routeee=new ArrayList<City>();
          for (int i = 0; i < route.size() ; i++) {
            routeee.add(cities.get(route.get(i)));
          }
          descript=CityMetadata.getMetaResult(routeee);
        }
        if (num_trail > 800) {
          min_route_length = Math.max(3, min_route_length - 2);
        }
        if (num_trail > 900) {
          min_route_length = 3;
        }
        // Check how many times we have tried.
        num_trail++;
        if (num_trail > 1000) {
          can_find_a_route = false;
          break;
        }
      } while (route_str == null || drawn_routes.contains(route_str) ||
               route == null || route.size() < min_route_length ||
               existing_route_description.contains(descript));
      // If we can not find any new example routes, break the process.
      if (!can_find_a_route)
        break;
      drawn_routes.add(route_str);
      existing_route_description.add(descript);
      g.setFont(new Font("SansSerif", Font.BOLD, 12));
      y += 10;  // padding from the previous route
      g.drawString(descript, 5, y);
      y += 15;
      g.setFont(new Font("SansSerif", Font.PLAIN, 12));
      y = drawMultilineExampleRoute(route_str, g, 5, y);
      addToExampleLinks(route);
     if(ll==0)
     {
    	 route1=route;
     }
     if(ll==1)
     {
    	 route2=route;
     }
      ll=1;
      for (Integer i : route) {
        if (route_str.indexOf(cities.get(i).name) != -1)
          finalcity[i] = true;
      }
    }
    
    
  }

  private City getCityByName(String name){
    Iterator<City> it = cities.iterator();
    while(it.hasNext()){
      City city = it.next();
      if(name.equalsIgnoreCase(city.name))
        return city;
    }
    return null;
  }

  public String name() throws Exception {
    return _CNAME;
  }

  public Color color() throws Exception {
    return _CCOLOR;
  }

  public boolean interactive() throws Exception {
    return false;
  }        

  int page_width = 600;
  int example_route_height = 180;
  int graph_width = 577, graph_height= 410;
  int zoom_graph_width = 350, zoom_graph_height= 200;

  public float mapX(double x, double width){
    return (float) (((x + 180 + 360) * width/360 ) % width);
  }

  public float mapY(double y, double height){
    y = (float) (y * Math.PI / 180.0);
    double normalized = Math.log(Math.tan(Math.PI / 4 + y / 2));
    //double CUT = Math.PI;
    double CUT = 2;
    double projection = (-normalized + CUT) * (height / (2 * CUT));
    return (float) projection;
  }

  private void drawLink(Graphics2D g, double x1, double y1, double x2, double y2, double
      map_width, double map_height) {
    double image_x1 = mapX(x1, map_width);
    double image_x2 = mapX(x2, map_width);
    double image_y1 = mapY(y1, map_height);
    double image_y2 = mapY(y2, map_height);
    if (x2 < x1 - 30) {
      g.drawLine((int) image_x1, (int) image_y1, (int) (image_x2 + map_width), (int) image_y2);
      g.drawLine((int) (image_x1 - map_width), (int) image_y1, (int) image_x2, (int) image_y2);
    } else {
      g.drawLine((int) image_x1, (int) image_y1, (int) image_x2, (int) image_y2);
    }
  }

  private void drawGraph(Graphics2D g, GRAPH_TYPE graph_type, double width, double height) {
	  drawMapBackground(g, (int) width, (int) height);
	  g.setFont(new Font(g.getFont().getName(), Font.BOLD, 10));
    int num_city = cities.size();
    //g.setColor(new Color(20, 20, 120));
    g.setColor(Color.WHITE);
    int num_drawn_link_at_city[] = new int[num_city];
    for (int i = 0; i <num_city; i++)
      num_drawn_link_at_city[i] = 0;

/*
    for (int i = 0; i < num_city; i++) {
      for (int j = 0; j < num_city; j++) {
        //if ((graph_type == GRAPH_TYPE.WHOLE_MAP && dominant_links[i][j]) ||
        //    (graph_type == GRAPH_TYPE.DETAILED_MAP && reachable_links[i][j])) {
        //if ((graph_type == GRAPH_TYPE.WHOLE_MAP && example_links[i][j]) ||
        //    (graph_type == GRAPH_TYPE.DETAILED_MAP && example_links[i][j])) {
        if (reachable_links[i][j]) {
          boolean clear_to_draw = true;
          int num_near_links = 0;
          for (int k = 0; k < num_city; k++) {
            if ((Math.abs(mapX(cities.get(i).x, width) - mapX(cities.get(k).x, width)) < 40 &&
                 Math.abs(mapY(cities.get(i).y, height) - mapY(cities.get(k).y, height)) < 40) ||
                (Math.abs(mapX(cities.get(j).x, width) - mapX(cities.get(k).x, width)) < 40 &&
                 Math.abs(mapY(cities.get(j).y, height) - mapY(cities.get(k).y, height)) < 40)) {
              num_near_links += num_drawn_link_at_city[k];
            }
          }
          if (num_near_links < 7 && num_drawn_link_at_city[i] < 5 &&
              num_drawn_link_at_city[j] < 5) {
            City src = cities.get(i);
            City dest = cities.get(j);
            drawLink(g, src.x, src.y, dest.x, dest.y, width, height);
            num_drawn_link_at_city[i]++;
            num_drawn_link_at_city[j]++;
          }
        }
      }
    }
*/

    int num_failed = 0;
    int num_trail = 0;
    boolean links_drawn[][] = new boolean[num_city][num_city];
    while (true) {
      ArrayList<Integer> route = Util.FindRandomRoute(reachable_links, start_city_idx);
      boolean clear_to_draw = true;
      for (int ri = 0; ri < route.size(); ri++) {
        int i = route.get(ri);
        int j = route.get((ri + 1) % route.size());
        int num_near_links = 0;
        for (int k = 0; k < num_city; k++) {
          if ((Math.abs(mapX(cities.get(i).x, width) - mapX(cities.get(k).x, width)) < 30 &&
               Math.abs(mapY(cities.get(i).y, height) - mapY(cities.get(k).y, height)) < 30 ) ||
              (Math.abs(mapX(cities.get(j).x, width) - mapX(cities.get(k).x, width)) < 30 &&
               Math.abs(mapY(cities.get(j).y, height) - mapY(cities.get(k).y, height)) < 30)) {
            num_near_links += num_drawn_link_at_city[k];
          }
        }
        if (num_near_links < 20 && num_drawn_link_at_city[i] < 15 &&
            num_drawn_link_at_city[j] < 15) {
        } else {
          clear_to_draw = false;
        }
      }
      if (clear_to_draw) {
        for (int ri = 0; ri < route.size(); ri++) {
          int i = route.get(ri);
          int j = route.get((ri + 1) % route.size());
          City src = cities.get(i);
          City dest = cities.get(j);
          if (!links_drawn[i][j]) {
            drawLink(g, src.x, src.y, dest.x, dest.y, width, height);
            num_drawn_link_at_city[i]++;
            num_drawn_link_at_city[j]++;
            links_drawn[i][j] = true;
          }
        }
      } else {
        num_failed++;
      }
      if (num_failed > 200)
        break;
      num_trail++;
      if (num_trail > 2000)
        break;
    }

    // Draw the longest route.
    ArrayList<Integer> longest_route =
        Util.findLongestRoute(cities, reachable_links, start_city_idx);
    for (int i = 0; i < longest_route.size(); i++) {
      City src = cities.get(longest_route.get(i));
      City dest = cities.get(longest_route.get((i + 1) % longest_route.size()));
      g.setColor(Color.BLACK);
      drawLink(g, src.x, src.y, dest.x, dest.y, width, height);
    }
    for (int i = 0; i < longest_route.size(); i++) {
      City src = cities.get(longest_route.get(i));
      g.setColor(Color.BLACK);
      g.fillOval((int)mapX(src.x, width) - 2, (int)mapY(src.y, height) - 2, 4, 4);
    }

    // Draw city names.
    ArrayList<Integer> drawn_cities = new ArrayList<Integer>();
    for (int i = 0; i < cities.size(); i++) {
      if (in_degree[i] > 0) {
        City city = cities.get(i);
        g.setColor(Color.BLACK);
        //g.drawOval((int)mapX(city.x, width) - 1, (int)mapY(city.y, height) - 1, 2, 2);
        g.fillOval((int)mapX(city.x, width) - 2, (int)mapY(city.y, height) - 2, 4, 4);
        g.setColor(Color.GRAY);
        //g.drawString(city.name, mapX(city.x, width) + 3, mapY(city.y, height));
        boolean clear_to_draw = true;
        for (int j = 0; j < drawn_cities.size(); j++) {
          City check_city = cities.get(drawn_cities.get(j));
          if (Math.abs(mapX(city.x, width) - mapX(check_city.x, width)) < 50 &&
              Math.abs(mapY(city.y, height) - mapY(check_city.y, height)) < 20) {
            clear_to_draw = false;
            break;
          }
        }
        if (clear_to_draw && i != start_city_idx) {
          drawn_cities.add(i);
          g.setColor(new Color(200, 200, 200));
          g.drawString(city.name, mapX(city.x, width) + 4, mapY(city.y, height) + 1);		    		
          g.setColor(Color.BLACK);
          g.drawString(city.name, mapX(city.x, width) + 3, mapY(city.y, height));		    		
          finalcity[i] = true;
        }
      }
    }

	  g.setFont(new Font(g.getFont().getName(), Font.BOLD, 12));
    g.setColor(new Color(10, 10, 60));
    g.drawString(start_city.name, mapX(start_city.x, width) + 4, mapY(start_city.y, height) + 1);
    g.setColor(new Color(255, 100, 100));
    g.drawString(start_city.name, mapX(start_city.x, width) + 3, mapY(start_city.y, height));		    		
    finalcity[start_city_idx] = true;
  }
  private void drawMapBackground(Graphics2D g, int width, int height) {
	    try {
	      File file = new File("GameFiles/G4-map.png");
	      BufferedImage image = ImageIO.read(file);
	      g.drawImage(image, 0, 0, width, height, null, null);
	    } catch (IOException e) {
	      e.printStackTrace();
	    }
	  }

  private void drawOtherCities(Graphics2D g) {
	  int x = 10, y = 18;
	  int line = 0;
    //start coordinate (x,y)
    String city_str = "";

    g.setColor(Color.BLACK);
    g.setFont(new Font("SansSerif", Font.BOLD, 14));

    boolean flagCity = false;
    //System.out.println("other cities test");
    for (int i=0; i<num_city; i++){
      if (!finalcity[i] && in_degree[i] > 0){ //false: need to print out
        //System.out.println(cities.get(i).name);
        flagCity = true;
        break;
      }
    }
    if(!flagCity){
      //g.drawString("All cities are shown(for test to delete)", x, y);
      return;  //if no city to display, return directly

    }

    //else, display
    Rectangle bound = g.getClipBounds();
    g.setColor(new Color(20, 20, 120));
    g.drawRoundRect(bound.x + 2, bound.y + 2, bound.width - 4, bound.height - 4, 6, 6);

    g.drawString("Other Cities you can Visit:", x, y);

    g.setFont(new Font("SansSerif", Font.PLAIN, 12));

    y += 18;
    int num_missing_city = 0;
    for (int i=0; i<num_city; i++){
      if (!finalcity[i] && in_degree[i] > 0){ //false: need to print out
        if (cities.get(i).name.length() > 10 ||
            (x > 90 && y > 180)) {
          num_missing_city++;
          continue;
        }
        g.drawString(cities.get(i).name, x, y);
        y += 15;
        if (y > 190) {
          y = 36;
          x += 90;
        }
      }
    }
    if (num_missing_city > 0) {
      g.drawString("(" + num_missing_city + " more cities)", x, y);
    }

    if(line == 0 ){ //only one line not full
      g.drawString(city_str, x, y);
    }
  }  //end of function drawOtherCities
}

